package cn.nawang.ebeim.client.version;

/**
 * Suppose a sorted array is rotated at some pivot unknown to you beforehand.
 * (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
 * Find the minimum element.
 * You may assume no duplicate exists in the array.
 *
 * Created by GanJc on 2016/2/25.
 */
public class FindMinimuminRotatedSortedArray {

    public static void main(String[] args) {
        int a [] = {4,5,6,7,0,1,2,3};//0
        findMinimumInRotatedSortedArray(a);
        int b [] = {5,6,7,1,2,3,4};//1
        findMinimumInRotatedSortedArray(b);
        int c [] = {9,10,11,22,33,2,3,4,5,6,7};  //2
        findMinimumInRotatedSortedArray(c);
        int  d[] = {};//0
        findMinimumInRotatedSortedArray(d);
    }

    public static void findMinimumInRotatedSortedArray(int [] a){
        if(a.length==0){
            System.out.println(0);
            return;
        }
        int start = 0;
        int stop = a.length - 1;
        int min = (start + stop) / 2;
        while (start<stop-1){
            if(a[start]<a[min]){
                start = min;
                min = (start+stop)/2;
            }else {
                stop = min ;
                min = (start+stop)/2;
            }
        }
//        System.out.println(start);
//        System.out.println(stop);
        int result = a[start] < a[stop] ? a[start] : a[stop];
        System.out.println(result);
    }


}
